package cn.z2huo.algorithm.sort.swapSort.quickSort;

import java.util.Random;

/**
 * 快速排序，随机获取基准
 * 两年前写的
 *
 * 作者： 张一卓
 * 时间： 2020/1/14 16:52
 */
public class QuickSorting2_2 {
    Random random = new Random();

    public void sort(int[] array, int left, int right) {
        if (array == null) {
            return;
        }
        if (left >= right) {
            return;
        }
        int low = left, high = right;
//        int centerPosition = 3;
        int centerPosition = random.nextInt(right-left+1) + left;
        int centerValue = array[centerPosition];
        while (low < high) {
            // 从序列末端寻找比 centerValue 小的元素
            while (array[high] >= centerValue && low < high && high > centerPosition) {
                high--;
            }
            if (low < high) {
                array[centerPosition] = array[high];
                centerPosition = high;
            }
            // 从序列前端寻找比 centerValue 大的元素
            while (array[low] <= centerValue && low < high && low < centerPosition) {
                low++;
            }
            if (low<high){
                array[centerPosition] = array[low];
                centerPosition = low;
            }
        }
        // 当low和high重合后，给基准元素赋值，因为在循环中只更新了基准元素的位置
        array[centerPosition] = centerValue;

        sort(array, left, centerPosition-1);
        sort(array, centerPosition + 1, right);
    }
}